package com.sourcetrip.my.abs;

import com.sourcetrip.my.LinkedListQueueV0;
import com.sourcetrip.my.StackByLinkedListV0;
import com.sourcetrip.my.inter.BinaryTree;
import com.sourcetrip.my.inter.Stack;
import com.sourcetrip.my.modle.TreeNode;
import com.sourcetrip.utils.Visitor;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2020/12/14
 * @description: 二叉树抽象类 实现了以下几个接口：
 * 1.size();
 * 2.isEmpty();
 * 3.clear();
 * 4.isComplete();
 * 5.height();
 * 6.四个遍历：preorder;inorder;postorder;levelOrder;
 * --
 * 增删改让 BST 实现
 */
public abstract class AbstractBinaryTree<E> implements BinaryTree<E> {

	/**
	 * 容量
	 */
	protected int size;

	/**
	 * 根节点
	 */
	protected TreeNode<E> root;


	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void clear() {
		root = null;
		size = 0;
	}

	/**
	 * 遍历节点(通过 循环的方式)查找元素
	 * 既然是查找，那就遍历即可
	 * 没有根据二叉查找树的特征进行查找！这里只是单纯的遍历
	 * @param element
	 * @return
	 */
	@Override
	public TreeNode<E> node(E element) {
		TreeNode<E> cur = this.root;
		if (cur == null) {
			return null;
		}
		//如果 元素 是 null
		if (element == null) {
			//看起来还是 preorder 最简单了
			Stack<TreeNode<E>> stack = new StackByLinkedListV0<>();
			stack.push(cur);
			while (!stack.isEmpty()) {
				cur = stack.pop();
				while (cur.left != null) {
					//compare root
					if (cur.element == null) {
						return cur;
					}
					if (cur.right != null) {
						stack.push(cur.right);
					}

					cur = cur.left;
				}
				//leftest node
				if (cur.element == null) {
					return cur;
				}
				if (cur.right != null) {
					stack.push(cur.right);
				}
			}
		} else {
			//use inorder
			Stack<TreeNode<E>> stack = new StackByLinkedListV0<>();
			stack.push(cur);
			boolean readLeft = false;
			while (!stack.isEmpty()) {
				cur = stack.pop();
				while (cur.left != null && !readLeft) {
					stack.push(cur);
					cur = cur.left;
				}
				//leftest node
				if (element.equals(cur.element)) {
					return cur;
				}

				if (cur.right != null) {
					stack.push(cur.right);
					readLeft = false;
				}else {
					readLeft = true;
				}
			}
		}
		return null;
	}

	/**
	 * 判断是否为完全二叉树
	 * LeetCode 958
	 * 用 LevelOrder 来进行判断
	 * 我的写法没有问题，只要借助 levelOrder 的框架就可以实现了！
	 * 而且情况也不复杂就一种情况
	 *
	 * @return
	 */
	@Override
	public boolean isComplete() {
		LinkedListQueueV0<TreeNode<E>> queue = new LinkedListQueueV0<>();
		if (root == null) {
			return false;
		}

		TreeNode<E> cur = this.root;
		//将 根节点 入队
		queue.enQueue(cur);
		// 当出现一个节点没有子树时，后面肯定不能再有子树了！
		boolean noMoreChild = false;
		while (!queue.isEmpty()) {
			cur = queue.deQueue();
			if (cur.left != null) {
				if (noMoreChild) {
					return false;
				}
				queue.enQueue(cur.left);
			} else {
				//如果一个节点的左子树为空，但是右子树非空
//				if (cur.right != null) {
//					return false;
//				}
				noMoreChild = true;
			}
			//此时，要么 left != null
			if (cur.right != null) {
				if (noMoreChild) {
					return false;
				}
				queue.enQueue(cur.right);
			} else {
				noMoreChild = true;
			}
		}
		return true;
	}

	/**
	 * 获取二叉树的高度
	 * LeetCode 104. 二叉树的最大深度
	 *
	 * @return
	 */
	@Override
	public int height() {
		return getNodeHeight(root);
	}

	//region	let Binary-Search-Tree realize

	/**
	 * 获取前驱节点
	 *
	 * @param node
	 * @return
	 */
	@Override
	public abstract TreeNode<E> predecessor(TreeNode<E> node);

	@Override
	public abstract TreeNode<E> successor(TreeNode<E> node);

	//endregion


	@Override
	public void preorder(Visitor<E> visitor) {
		preorder(root, visitor);
	}

	@Override
	public void inorder(Visitor<E> visitor) {
		inorder(root, visitor);
	}

	@Override
	public void postorder(Visitor<E> visitor) {
		postorder(root, visitor);
	}

	@Override
	public void levelOrder(Visitor<E> visitor) {
		levelOrder(root, visitor);
	}

	//region	BinaryTreeInfo 的接口

	@Override
	public Object root() {
		return root;
	}

	@Override
	public Object left(Object node) {
		return ((TreeNode<E>) node).left;
	}

	@Override
	public Object right(Object node) {
		return ((TreeNode<E>) node).right;
	}

	@Override
	public Object string(Object node) {
		TreeNode<E> myNode = (TreeNode<E>) node;
		String parentString = "null";
		if (myNode.parent != null) {
			parentString = myNode.parent.element.toString();
		}
		return myNode.element + "_p(" + parentString + ")";
	}

	//endregion

	//region	private methods

	/**
	 * 先序遍历（根左右）
	 * 迭代的写法
	 * LeetCode 144. 二叉树的前序遍历
	 * https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
	 *
	 * @param node
	 * @param visitor
	 */
	protected void preorder(TreeNode<E> node, Visitor<E> visitor) {
		StackByLinkedListV0<TreeNode> stack = new StackByLinkedListV0<>();
		if (node == null) {
			return;
		}
		stack.push(node);
		TreeNode<E> cur = node;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			while (cur.left != null) {

				if (visitor.stop) {
					return;
				} else {
					visitor.visit(cur.element);
				}
				if (cur.right != null) {
					stack.push(cur.right);
				}
				cur = cur.left;
			}
			if (visitor.stop) {
				return;
			} else {
				visitor.visit(cur.element);
			}
			if (cur.right != null) {
				stack.push(cur.right);
			}
		}
	}

	/**
	 * 中序遍历
	 * 迭代的写法
	 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
	 * LeetCode 94. 二叉树的中序遍历
	 *
	 * @param node
	 * @param visitor
	 */
	protected void inorder(TreeNode<E> node, Visitor<E> visitor) {
		StackByLinkedListV0<TreeNode> stack = new StackByLinkedListV0<>();
		if (node == null) {
			return;
		}
		stack.push(node);
		TreeNode<E> cur = node;
		boolean readLeft = false;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			while (cur.left != null && !readLeft) {
				stack.push(cur);
				cur = cur.left;
			}
			//直至最左的 左子节点
			if (visitor.stop) {
				return;
			} else {
				visitor.visit(cur.element);
			}

			if (cur.right != null) {
				stack.push(cur.right);
				readLeft = false;
			} else {
				readLeft = true;
			}
		}

	}

	/**
	 * 后序遍历
	 * LeetCode 145
	 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
	 *
	 * @param node
	 * @param visitor
	 */
	protected void postorder(TreeNode<E> node, Visitor<E> visitor) {
		List<Integer> res = new ArrayList<>();
		if (node == null) {
			return;
		}
		StackByLinkedListV0<TreeNode> stack = new StackByLinkedListV0<>();
		stack.push(node);
		TreeNode<E> cur = node;
		boolean readLeft = false;
		TreeNode prev = null;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			while (cur.left != null && !readLeft) {
				stack.push(cur);
				cur = cur.left;
			}

			if (cur.right != null && cur.right != prev) {
				stack.push(cur);
				stack.push(cur.right);
				readLeft = false;
			} else {
				//处理
				if (visitor.stop) {
					return;
				} else {
					visitor.visit(cur.element);
				}

				prev = cur;
				readLeft = true;
			}
		}
		return;
	}

	/**
	 * 层序遍历
	 *
	 * @param node
	 * @param visitor
	 */
	protected void levelOrder(TreeNode<E> node, Visitor<E> visitor) {
		if (node == null) {
			return;
		}
		//通过 队列辅助层次遍历
		LinkedListQueueV0<TreeNode<E>> queue = new LinkedListQueueV0<>();
		queue.enQueue(node);
		TreeNode<E> cur = node;
		while (!queue.isEmpty()) {
			cur = queue.deQueue();
			if (cur.left != null) {
				queue.enQueue(cur.left);
			}
			if (cur.right != null) {
				queue.enQueue(cur.right);
			}
			//处理 cur 节点
			if (visitor.stop) {
				return;
			} else {
				visitor.visit(cur.element);
			}
		}
	}

	/**
	 * 获取节点的高度
	 *
	 * @param node
	 * @return
	 */
	private int getNodeHeight(TreeNode<E> node) {
		if (node == null) {
			return 0;
		}

		return Math.max(getNodeHeight(node.left), getNodeHeight(node.right)) + 1;
	}

	//endregion
}
